\begin{abstract}
We study how to spread $k$ tokens of information to every node on an
$n$-node dynamic network, the edges of which are changing at each
round.  This basic {\em gossip problem}\/ can be completed in $O(n +
k)$ rounds in any static network, and determining its complexity in
dynamic networks is central to understanding the algorithmic limits
and capabilities of various dynamic network models.  Our focus is on
token-forwarding algorithms, which do not manipulate tokens in any way
other than storing and forwarding them.

We first consider a worst-case adversarial model in which an arbitrary
connected network is chosen for each round by an online adversary, and
each node is allowed to broadcast one token to all neighbors in each
round.  We show that $\Omega(n + nk/\log n)$ rounds are needed for any
{\em deterministic} (centralized or distributed) token-forwarding
algorithm, thus resolving an open problem raised
in~\cite{kuhn+lo:dynamic}.  Our lower bound extends to randomized
algorithms if the adversary knows, at the start of each round, the
random choices made by the algorithm in the round, but is unaware of
future random choices.  The bound also applies to a wide class of
initial token distributions, including {\em well-mixed}\/ ones in
which each node has each token independently with a constant
probability.  Our result shows that one cannot obtain $o(nk)$-round
token-forwarding algorithms for gossip in the above worst-case
adversarial model, thus motivating us to study weaker models.

We propose a simple randomized distributed algorithm where in each
round, along every edge $(u,v)$ a token is exchanged, selected
uniformly from the symmetric difference of the sets of tokens held by
node $u$ and node $v$.  We prove that starting from any well-mixed
distribution of tokens, this algorithm solves the gossip problem in
$O((n+k)\log n)$ rounds with high probability, against online
oblivious adversaries.  We then show how the above uniform selection
problem can be solved with $O(\log^{1.5} n)$ communication bits,
making the overall algorithm communication-efficient.

We next present a centralized offline algorithm that solves the gossip
problem for every initial distribution in $O((n + k)\log^2 n)$ rounds
for any dynamic network.  As in the previous algorithm, here we allow
each node to send a distinct token to each of its neighbors in each
round.  Finally, we present an $O(n \min\{k, \sqrt{k \log n}\})$-round
centralized offline algorithm for the model where each node can only
broadcast a single token to all of its neighbors in each round.
\end{abstract}

\junk{
We next present two fast algorithms that can solve the gossip problem
in $O((n + k)\log^2 n)$ rounds with high probability, which is within
a polylogarithmic factor of the best possible time. Our first
algorithm is a {\em distributed randomized}\/ algorithm that works for
any well-mixed distribution under an oblivious adversary.  A key
ingredient of this algorithm is an $O(\log n)$-bit protocol for
sampling uniformly at random from the symmetric difference of two sets
stored at two communicating nodes, a result that may be of independent
interest in communication complexity.  Our second algorithm is
centralized and offline, and solves gossip for every starting
distribution in $O((n + k)\log^2 n)$ rounds for any dynamic network.
Both of these upper bounds assume that each node can send a distinct
message to each of its neighbors in each round.  We also present
weaker upper bounds for the model where each node can only broadcast a
single message to all of its neighbors in each round.
}

\junk{
The focus of this paper is understanding  complexity the power of token-forwarding
algorithms, which do not manipulate tokens in any way other than
storing and forwarding them.  
}

\junk{probabilistic method and shows that the bound holds for ``most"
starting token distributions.}

\junk{improving their lower bound of $\Omega(n \log k)$, and matching
  their upper bound of $O(nk)$ to within a logarithmic factor.  Our
  lower bound extends to centralized algorithms and also to randomized
  algorithms against an adversary that, in each round, knows the
  randomness used by the algorithm in that round. }

\junk{
  We present two polynomial-time centralized
%token-forwarding algorithms for $k$-gossip in this offline setting:
%(1) an $O(\min\{nk, n\sqrt{k \log n}\})$ round algorithm, and (2) an
%$(O(n^\eps), O(\log n))$ bicriteria approximation algorithm, for any
%$\eps > 0$, which means that our algorithm completes in $O(n^\eps)$
%times the optimal number of rounds and the number of tokens
%transmitted on any edge is $O(\log n)$ in each round.

%Our results are a step towards understanding the power
%and limitations of token-forwarding algorithms and our lower and upper
%bound techniques can be useful in addressing related problems in
%dynamic networks.
}

\junk{The problem is especially challenging in dynamic networks where
  the network topology can change arbitrarily from round to round and
  can be controlled by an adversary.  }
